The present invention relates generally to a method and apparatus for implementing an error correction coding scheme for use with digital-to-digital coding. More particularly, the present invention relates to a method of and apparatus for providing efficient error correction coding for use with modulation codes having arbitrary constraints.
The use of modulation codes in connection with magnetic and optical data storage systems is widespread and the advantages of modulation coding are well known. For example, in U.S. Pat. No. 3,689,899, entitled Run-Length Limited Variable Length Coding With Error Propagation Limitation, a run-length limited variable length code with error propagation limitation is disclosed. U.S. Pat. No. 4,146,909, issued Mar. 27, 1979 for a Sync Pattern Encoding System for Run-Length Limited Codes, discloses a system in which a continuous bit stream of the proper character is continuously supplied to an encoder.
In such storage systems, a 1 is usually used to represent a transition between the up and down states of the recording waveform, while a 0 is used to represent no change in the waveform. However, in practice, an unconstrained sequence of 1's and 0's is undesirable. For example, a long sequence of uninterrupted 0's results in a loss of synchronization when the data is self-clocking. Also, the imbalance between the up and down states of the recording waveform may result in significant charge accumulation in the electronic circuitry which results in forcing the system beyond acceptable levels of operation.
The objective of modulation coding is therefore to create a one-to-one correspondence between sequences of user data, which are usually streams of random binary digits, and constrained binary sequences. The nature of the constraints imposed upon the modulation signal is determined by the system designer and is dependent upon the particular characteristics of the system under consideration.
A typical set of restrictions imposed upon a recording sequence is the so-called (d,k; c) constraint. In this constraint, the d is the minimum allowed run-length of 0's, the k is the maximum allowed run-length of 0's and the c is the maximum charge that the recording waveform is permitted to accumulate. In addition, certain sequences of bits may be reserved for special purposes, such as signalling at the beginning of a block, and thus be banned from appearing at all in the modulated waveform. A (2,7) run length limited (RLL) code is a commonly used example of such a constraint which is used in connection with magnetic and optical data storage.
The minimum run-length constraint d is somewhat more subtle than the k and c constraints and thus needs further elaboration. In practice, the physical separation between successive transitions on the recording medium cannot be made arbitrarily small. The minimum distance between transitions is a function of the structural and/or magnetic properties of the medium, as well as the characteristics of the read/write head. Thus, the gap-width of the magnetic recording head or the wavelength of light in optical recording, together with the structural/magnetic features of the recording medium, determine the minimum distance.
It is useful to measure distance along the track in terms of .DELTA.. Thus, in the discussion which follows, density is defined as the number of bits per .DELTA..
If there are no constraints on the minimum run-length of 0's, for example, if d equals 0, then each modulation bit will occupy one interval of length .DELTA.. Since the number of modulation bits is always greater than the number of data bits, the overall recording density becomes less than 1 data bit per .DELTA.. If, on the other hand, d is not equal to 0, then d+1 modulation bits can be packed in every interval of length .DELTA..
When the code parameters are properly chosen, the higher density of modulation bits can translate into a higher density recording of data bits. In that manner, the overall density becomes greater than 1 data bit per .DELTA.. However, the price of such an increase in capacity is the reduced period of time available to each modulation bit. If t is defined as the time that the read/write head dwells on an interval of length .DELTA., then the time window available to each modulation bit will be t/(d+1).
The present invention is directed to a method of and apparatus for providing error correction coding (ECC) for modulation coding with arbitrary constraints, such as for 2,7 RLL coding. However, as the modulation constraints become less restrictive, presently known error correction coding techniques do not perform their function in an efficient nor accurate manner. The error correction coding scheme of the present invention overcomes those disadvantages of prior art ECC schemes.
The present invention is also directed to an error correction scheme for preventing random errors that occur infrequently but yet corrupt modulation code words in a few unknown locations. Some of those errors may be readily detectable because they violate the modulation coding rules. However, depending upon the severity of the arbitrary constraints used with the modulation coding, in practice that type of error correction may not have the desired power.
One way in which to find the closest code word (in the Hamming sense) to the readout sequence is to utilize a Viterbi decoder. The applicability of this type of decoder for minimum distance decoding arises from the fact that modulation coding is based upon state transition tables. Thus, utilizing a Viterbi decoder during the readout process, a code word can be identified that not only satisfies all of the modulation constraints, but is also closest to the read-back waveform for a given measure of distance.
However, not all errors can be recovered in this manner. The more restrictive the modulation constraints become, the better their error-correction capabilities. However, it has been experimentally found by the inventors that (d, k; c) constraints are not powerful enough for correcting such random errors. The only instance in which the use of such constraints is powerful enough is in the case of a very small c, which results in small rates and thus much less useful constraints.